package Rangel.common.convex;

import math.geom2d.Point2D;
import math.geom2d.line.Line2D;
import math.geom2d.polygon.Polygon2D;
import math.geom2d.polygon.convhull.JarvisMarch2D;

import java.awt.*;
import java.util.*;
import java.util.List;

public class CompositeConvexHull implements IConvexHull {

    private List<Point> points;

    private Set<Point> addedPoints;

    private Set<Point> removedPoints;

    private Polygon convexHullPolygon;

    private JarvisMarch2D jarvisMarchCalculator;

    public CompositeConvexHull() {
        points = new ArrayList<>();
        jarvisMarchCalculator = new JarvisMarch2D();
        addedPoints = new HashSet<>();
        removedPoints = new HashSet<>();
    }

    @Override
    public Polygon getConvexPolygon() {//获取凸多边形
        if (isDataUpdated()) {
            convexHullPolygon = updateConvexPolygon();
        }
        return convexHullPolygon;
    }

    public Polygon updateConvexPolygon() {
        Polygon returnValue;
        if (convexHullPolygon != null) {
            Set<Point> onVerticesRemovedPoints = new HashSet<>();
            for (Point removedPoint : removedPoints) {
                for (int i = 0; i < convexHullPolygon.npoints; i++) {//凸包多边形的点
                    if (removedPoint.x == convexHullPolygon.xpoints[i]
                            && removedPoint.y == convexHullPolygon.ypoints[i]) {
                        onVerticesRemovedPoints.add(removedPoint);
                        break;
                    }
                }
            }

            removedPoints.removeAll(onVerticesRemovedPoints);
            points.removeAll(removedPoints);
                        removedPoints = onVerticesRemovedPoints;

                        Set<Point> onVerticesAddedPoints = new HashSet<>();//在图形上的添加点
                        Set<Point> outerAddedPoints = new HashSet<>();//内部
                        Set<Point> innerAddedPoints = new HashSet<>();//外部

                        for (Point addedPoint : addedPoints) {
                            for (int i = 0; i < convexHullPolygon.npoints; i++) {
                                if (addedPoint.x == convexHullPolygon.xpoints[i]
                                        && addedPoint.y == convexHullPolygon.ypoints[i]) {
                                    onVerticesAddedPoints.add(addedPoint);
                                } else if (convexHullPolygon.contains(addedPoint)) {
                                    innerAddedPoints.add(addedPoint);
                                } else {
                        outerAddedPoints.add(addedPoint);
                    }
                }
            }

            addedPoints.removeAll(innerAddedPoints);
            addedPoints.removeAll(onVerticesAddedPoints);

            points.addAll(innerAddedPoints);
            points.addAll(onVerticesAddedPoints);

            addedPoints = outerAddedPoints;
        }


        if (removedPoints.isEmpty() && addedPoints.isEmpty()) {
            returnValue = convexHullPolygon;
        } else if (convexHullPolygon != null && removedPoints.isEmpty() && !addedPoints.isEmpty()) {
            addPointsToConvexHull(addedPoints);
            addedPoints.clear();
            returnValue = convexHullPolygon;
        } else {
            points.removeAll(removedPoints);
            points.addAll(addedPoints);

            addedPoints.clear();
            removedPoints.clear();

            List<Point2D> point2ds = convertPoints(points);
            Polygon2D polygon2d = jarvisMarchCalculator.convexHull(point2ds);
            returnValue = convertPolygon2d(polygon2d);
        }

        return returnValue;
    }

    /**
     * Adds the specified points to the convex hull without using the delegate.
     * 不使用分配将指定的点添加到凸包。
     * @param addedPoints Points to be added to the convex hull
     */
    private void addPointsToConvexHull(Set<Point> addedPoints) {//将点添加到凸包
        for (Point addedPoint : addedPoints) {
            Point centroid = new Point();//重心
            for (int i = 0; i < convexHullPolygon.npoints; i++) {
                centroid.x += convexHullPolygon.xpoints[i];
                centroid.y += convexHullPolygon.ypoints[i];
            }
            centroid.x /= convexHullPolygon.npoints;
            centroid.y /= convexHullPolygon.npoints;


            Line2D anchor = new Line2D(centroid.x, centroid.y, addedPoint.x, addedPoint.y);
            double anchorAngle = anchor.getHorizontalAngle();//获取水平角度

            double minAngle = 2 * Math.PI;
            double maxAngle = -2 * Math.PI;
            int minAngleVertexIndex = -1;//最小角度顶点索引
            int maxAngleVertexIndex = -1;
            for (int i = 0; i < convexHullPolygon.npoints; i++) {
                double angle = anchorAngle - new Line2D(convexHullPolygon.xpoints[i], convexHullPolygon.ypoints[i], addedPoint.x, addedPoint.y).getHorizontalAngle();
                if (angle > 2 * Math.PI) {
                    angle -= (2 * Math.PI);
                }
                if (angle < 0) {
                    angle += (2 * Math.PI);
                }

                if (angle > Math.PI / 2 && angle < 1.5 * Math.PI) {
                    angle = angle - Math.PI;
                } else if (angle >= 1.5 * Math.PI && angle <= 2 * Math.PI) {
                    angle = angle - 2 * Math.PI;
                }

                if (angle > maxAngle) {
                    maxAngle = angle;
                    maxAngleVertexIndex = i;
                }
                if (angle < minAngle) {
                    minAngle = angle;
                    minAngleVertexIndex = i;
                }
            }

                int[] xpoints = new int[convexHullPolygon.npoints + 2 - Math.abs(maxAngleVertexIndex - minAngleVertexIndex)];
                int[] ypoints = new int[convexHullPolygon.npoints + 2 - Math.abs(maxAngleVertexIndex - minAngleVertexIndex)];

                int newPointsIndex = 0;

                points.clear();

                for (int i = 0; i <= Math.min(minAngleVertexIndex, maxAngleVertexIndex); i++) {
                    xpoints[newPointsIndex] = convexHullPolygon.xpoints[i];
                    ypoints[newPointsIndex] = convexHullPolygon.ypoints[i];
                    points.add(new Point(xpoints[newPointsIndex], ypoints[newPointsIndex]));
                    newPointsIndex++;
                }

                xpoints[newPointsIndex] = addedPoint.x;
                ypoints[newPointsIndex] = addedPoint.y;
                points.add(new Point(xpoints[newPointsIndex], ypoints[newPointsIndex]));
                newPointsIndex++;

                for (int i = Math.max(minAngleVertexIndex, maxAngleVertexIndex);
                     i < convexHullPolygon.npoints;
                     i++) {
                    xpoints[newPointsIndex] = convexHullPolygon.xpoints[i];
                    ypoints[newPointsIndex] = convexHullPolygon.ypoints[i];
                    points.add(new Point(xpoints[newPointsIndex], ypoints[newPointsIndex]));
                    newPointsIndex++;
                }

                convexHullPolygon = new Polygon(xpoints, ypoints, newPointsIndex);
        }
    }

    @Override
    public void addPoint(int x, int y) {
        addPoint(new Point(x, y));
    }

    @Override
    public void addPoint(Point point) {
        if (removedPoints.contains(point)) {
            removedPoints.remove(point);
        } else {
            addedPoints.add(point);
        }
    }

    private boolean isDataUpdated() {
        return !addedPoints.isEmpty() || !removedPoints.isEmpty();
    }

    private static List<Point2D> convertPoints(List<Point> points) {
        List<Point2D> point2ds = new ArrayList<>();
        for (Point point : points) {
            point2ds.add(new Point2D(point.x, point.y));
        }
        return point2ds;
    }

    private static Polygon convertPolygon2d(Polygon2D polygon2d) {//转换2d多边形为多边形
        Collection<Point2D> vertices = polygon2d.getVertices();
        int[] xPoints = new int[vertices.size()];
        int[] yPoints = new int[vertices.size()];
        int i = 0;
        for (Point2D point2d : vertices) {
            xPoints[i] = (int) point2d.x;
            yPoints[i] = (int) point2d.y;
            i++;
        }
        return new Polygon(xPoints, yPoints, vertices.size());
    }

}
